This invention relates to a hardware network for use with a digital computer to implement a division function. In particular, this invention relates to apparatus which will produce multiple binary quotient bits for each iteration of the division operation. Further, this invention may operate in a computer arithmetic unit in a pipeline mode of operation.
Significant prior art in this field is represented in patents issued to the same assignee as the present application. A high-speed divider producing two quotient bits per iteration is shown in U.S. Pat. No. 3,293,418 issued to Thornton. A further development along similar lines is represented by U.S. Pat. No. 3,733,477 showing a division apparatus for producing three binary bits of partial quotient per iteration using three adders and logic circuits for selection functions.
Binary division apparatus as represented in the digital computer field is represented by two major classifications: restoring division and nonrestoring division. The restoring division sequence is essentially the standard long division process as taught to children in elementary schools. This method is primarily characterized in that if a new partial remainder is formed during a step of the division process which is negative, it is not used. Only positive remainders smaller than the divisor are allowed to be used.
Nonrestoring division is a process in which the sign of the remainder in each iteration of the division is used to determine whether to add or subtract the divisor in the next iteration of the division, rather than to determine whether or not to save the current remainder. Thus, the remainder is saved at every iteration of the division regardless of whether it is positive or negative. The present apparatus operates in a mode which may be characterized as nonrestoring. The two prior art patents would be characterized as restoring systems in the sense that only positive remainders are used. In fact, the process of selection of partial quotient bits in both prior art patents ensures that only positive remainders can be generated. Because of this feature, nothing is, in fact, restored in either prior art patent. However, it is clear that neither prior art patent shows the use of a negative remainder.
Another patent, not owned by the present assignee, U.S. Pat. No. 3,223,831 shows a divider in which two quotient bits are generated per iteration of the division and in which various logic circuits implement decision functions based on previous results. This patent does not however show the carry-save adders and logic circuitry of the present invention nor anticipate the present invention in anyway.